2019牛客暑期多校训练营（第五场）G - subsequeue 1 (一题我真的不会的题)

Diposting di

题意

给你两个由数字组成的字符串$S$,$T$ 长度为$1e3$，问你S中有多少个子序列的值大于字符串T；

思路

首先在比赛的时候一眼确定是$N^2$ 复杂度的DP，但是想了两三个小时却没想到怎么转移，各种构造$dp[i][j]$的含义。可是无功而返。

比赛结束后发现大家都用到了组合数。发现大家这题都用分两类来讨论做题。这时候才焕然大悟。

原来比T大的字符串可以分成两类根本不用瞎几把转移。

于是这题的解法很快就想到了，如果是大于的情况，那么只要第一个字符不是0，那么后面的几个字符串就随便取就行了。

大于的结束了接下来就是相等的情况。如果相等 那么肯定要考虑是从$S$串的哪个作为起点来构造子序列。并且这个S串的起点，的下一个点从哪里转移。这些都是可以DP的。于是我们基本的状态确定了，我们首先要确定目前构造到S串的哪个位置了。同时这个位置对于着T串的哪个位置，这样我们就可以开始转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
using namespace std;
const int maxn=4e3+50;
typedef long long ll;
const ll mod=998244353;
ll dp[maxn][maxn];
ll C[maxn][maxn];
void add(ll &a,ll b){
    a+=b;
    if(a>=mod)a-=mod;
}
char s[maxn],t[maxn];
int main(){
    std::ios::sync_with_stdio(false);
    int T;
    C[0][0]=1;
    for(int i=1;i<=3000;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i)C[i][j]=1;
            else add(C[i][j],C[i-1][j-1]+C[i-1][j]);
        }
    }
    cin>>T;
    while(T--){
        int n,m;
        cin>>n>>m;
        cin>>s+1>>t+1;
        for(int i=0;i<=n+10;i++){
            for(int j=0;j<=m+10;j++)dp[i][j]=0;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            if(s[i]=='0')continue;
            for(int j=m;j<=n;j++){
                add(ans,C[n-i][j]);
            }
        }
        ///dp[i][j]= 从后往前到当前S串第j的字符位置匹配到T串的第I个字符并且大于的个数
        for(int i=m;i;i--){
            for(int j=n;j;j--){
                dp[j][i]=dp[j+1][i];  ///因为包括了没有第j个字符的情况，所以如果第j+1个字符符合条件也可以
                if(t[i]==s[j])add(dp[j][i],dp[j+1][i+1]);
                /// 如果两个字符相同 那么答案就是少取这第J个字符同时还大于的数量
                if(t[i]<s[j])add(dp[j][i],C[n-j][m-i]);
                ///如果大于  那么答案就是后面的几个随便取几个就行了。
            }
        }
        cout<<(ans+dp[1][1])%mod<<endl;
    }
    return 0;
}